package oj;

public class NumOf51 {
    public int reversePairs(int[] nums) {
        return reversePairsInternal(nums,0,nums.length-1);
    }

    private int reversePairsInternal(int[] nums, int l,int r ) {
        if(l>=r){
            return 0;
        }
        int mid=l+(r-l)/2;
        int leftNum=reversePairsInternal(nums,l,mid);
        int rightNum=reversePairsInternal(nums,mid+1,r);
        if(nums[mid]>nums[mid+1]){
            return leftNum+rightNum+merge(nums,l,mid,r);
        }else {
            return leftNum+rightNum;
        }
    }

    private int merge(int[] nums, int l, int mid, int r) {
        int count=0;
        int[] tmp=new int[r-l+1];
        for (int i = l; i <=r ; i++) {
            tmp[i-l]=nums[i];
        }
        int i=l;
        int j=mid+1;
        for (int k = l; k <=r ; k++) {
            if(i>mid){
                nums[k]=tmp[j-l];
                j++;
            }else if(j>r){
                nums[k]=tmp[i-l];
                i++;
            }else if(tmp[i-l]<=tmp[j-l]){
                nums[k]=tmp[i-l];
                i++;
            }else {
                nums[k]=tmp[j-l];
                count+=mid-i+1;
                j++;
            }
        }
        return count;
    }
}
